package com.manman.algorithm.sort.base;

/**
 * @author: yeshengbin
 * @date: 2025/6/2 21:29
 * @description: 归并排序
 * 时间复杂度：O(nlogn)
 * 空间复杂度：O(n)
 * 稳定性：稳定
 * 原地排序：否
 */
public class MergeSort {

    public static void mergeSort(int[] arr) {
        sort(arr, 0, arr.length-1);
    }

    /**
     * 递归分割并排序子数组（分治的"分"步骤）
     * @param arr 待排序数组
     * @param left 子数组左边界索引（包含）
     * @param right 子数组右边界索引（包含）
     */
    public static void sort(int[] arr, int left, int right) {
        // 终止条件：当子数组只有1个元素（left == right）时不再分割
        if (right <= left) return;
        // 计算中间索引：使用 left + (right-left)/2 代替 (left+right)/2，防止整数溢出
        int mid = left + (right - left) / 2;
        // 递归排序左半部分子数组 [left, mid]
        sort(arr, left, mid);
        // 递归排序右半部分子数组 [mid+1, right]
        sort(arr, mid + 1, right);
        // 合并两个已排序的子数组（分治的"治"步骤）
        merge(arr, left, mid, right);
    }

    /**
     * 合并两个有序子数组（分治的"治"步骤）
     * @param arr 原数组（合并结果将覆盖原数组）
     * @param left 左子数组左边界索引（包含）
     * @param mid 左子数组右边界索引（包含），mid+1为右子数组左边界
     * @param right 右子数组右边界索引（包含）
     */
    public static void merge(int[] arr, int left, int mid, int right) {
        // 初始化双指针：i指向左子数组起始，j指向右子数组起始
        int i = left;
        int j = mid + 1;
        // 临时数组指针
        int k = 0;
        // 创建临时数组存储合并结果（长度为当前处理的子数组长度）
        int[] temp = new int[right - left + 1];
        // 合并阶段：比较左右子数组当前元素，将较小值存入临时数组
        while (i <= mid && j <= right) {
            // 保持稳定性：相等时优先取左子数组元素
            if (arr[i] <= arr[j]) {
                temp[k++] = arr[i++];
            } else {
                temp[k++] = arr[j++];
            }
        }
        // 处理左子数组剩余元素（右子数组已完全合并）
        while (i <= mid) {
            temp[k++] = arr[i++];
        }
        // 处理右子数组剩余元素（左子数组已完全合并）
        while (j <= right) {
            temp[k++] = arr[j++];
        }
        k = 0;
        // 将临时数组的合并结果复制回原数组对应位置
        while (left <= right) {
            arr[left++] = temp[k++];
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        mergeSort(arr);
        System.out.println("排序后的数组：");
        for (int i : arr) {
            System.out.print(i + " ");
        }
        System.out.println();
    }
}
